#include <iostream>
#include <iomanip>
#include <list>
#include "player.h"
#include "board.h"

using namespace std;

bool endOfGame(BOARD board, int gameState, char color);
int countColors(BOARD board, MOVE move, int yInc, int xInc, char color, list<MOVE> &cellsOfConnection);
void doStuff(int &count, int temp, list<MOVE> &cellsOfConnection, list<MOVE> &tempCellsOfConnections );
int gameStatus(BOARD board, MOVE move, char color, list<MOVE> &cellsOfConnection );
list<MOVE>* bustAMove(BOARD &board, MOVE move, char color, int &gameState);
list<MOVE>* userMoveHandler(BOARD &board, MOVE move, char color, int &gameState);
list<MOVE>* thinkingMachine(BOARD &board, MOVE &move, int &numMoves, int minNumMoves, int &gameState, char color);
list<MOVE>* getBestMove(BOARD &board, MOVE &move, char color);
list<MOVE>* compMoveHandler(BOARD &board, MOVE &move, char color, int &gameState);
void getUserMove(BOARD board, MOVE &move );
void printBoard(BOARD board);
void printXCells(list<MOVE> cellsOfConnection);

enum {WIN, LOSS, DRAW, NOTHING};

bool endOfGame(BOARD board, int gameState, char color)
{
  if(gameState == WIN)
    cout << "Color " << color << " wins!" << endl;
  else if(gameState == LOSS)
    cout << "Color " << color << " loses!" << endl; 
  else if((gameState == NOTHING) && (board.numMovesLeft() == 0))
    cout << "Draw." << endl;
  else
  {
    cout << "...game still in progress..." << endl;
    return false;
  }
  return true;
}




bool opportunity(BOARD board, MOVE move, int distance, char color)
{
  char userColor = (color == 'g') ? 'r' : 'g';
  int y = move.first;  
  int x = move.second; 
  bool check(false);
    
  //left
  if(((x-distance) >= 0) && (board.grid[y][x-distance].color == color))
  {
    check=true;
    //loop that checks between for user color
    for(int i = 1; i<distance; ++i)
    {
      if(board.grid[y][x-i].color == userColor)
        check=false;
    }
    if (check)
      return true;
  }

  //right
  if(((x+distance) <= 9) && (board.grid[y][x+distance].color == color))
  {
    check=true;
    //loop that checks between for user color
    for(int i = 1; i<distance; ++i)
    {
      if(board.grid[y][x+i].color == userColor)
        check=false;
    }
    if (check)
      return true;
  }

  //up
  if(((y-distance) >= 0) && (board.grid[y-distance][x].color == color))
  {
    check=true;
    //loop that checks between for user color
    for(int i = 1; i<distance; ++i)
    {
      if(board.grid[y-i][x].color == userColor)
        check=false;
    }
    if (check)
      return true;
  }

  //down
  if(((y+distance) <= 9) && (board.grid[y+distance][x].color == color))
  {
    check=true;
    //loop that checks between for user color
    for(int i = 1; i<distance; ++i)
    {
      if(board.grid[y+i][x].color == userColor)
        check=false;
    }
    if (check)
      return true;
  }

  //top left
  if(((y-distance) >= 0) && ((x-distance) >= 0) && (board.grid[y-distance][x-distance].color == color))
  {
    check=true;
    //loop that checks between for user color
    for(int i = 1; i<distance; ++i)
    {
      if(board.grid[y-i][x-i].color == userColor)
        check=false;
    }
    if (check)
      return true;
  }

  //top right
  if(((y-distance) >= 0) && ((x+distance) <= 9) && (board.grid[y-distance][x+distance].color == color))
  {
    check=true;
    //loop that checks between for user color
    for(int i = 1; i<distance; ++i)
    {
      if(board.grid[y-i][x+i].color == userColor)
        check=false;
    }
    if (check)
      return true;
  }

  //bottom left
  if(((y+distance) <= 9) && ((x-distance) >= 0) && (board.grid[y+distance][x-distance].color == color))
  {
    check=true;
    //loop that checks between for user color
    for(int i = 1; i<distance; ++i)
    {
      if(board.grid[y+i][x-i].color == userColor)
        check=false;
    }
    if (check)
      return true;
  }

  //bottom right
  if(((y+distance) <= 9) && ((x+distance) <= 9) && (board.grid[y+distance][x+distance].color == color))
  {
    check=true;
    //loop that checks between for user color
    for(int i = 1; i<distance; ++i)
    {
      if(board.grid[y+i][x+i].color == userColor)
        check=false;
    }
    if (check)
      return true;
  }

  return false;
}

int countColors(BOARD board, MOVE move, int yInc, int xInc, char color, list<MOVE> &cellsOfConnection)
{
  int count(0);
  int y(move.first+yInc);
  int x(move.second+xInc);
  while(board.grid[y][x].color == color)
  {
    cellsOfConnection.push_back(pair<int,int>(y,x));
    y+=yInc;
    x+=xInc;
    ++count;   
  }
  return count;
} 

void doStuff(int &count, int temp, list<MOVE> &cellsOfConnection, list<MOVE> &tempCellsOfConnections )
{
  if(temp>count) 
  {
    count = temp; 
    cellsOfConnection.clear();
    for(list<MOVE>::const_iterator it = tempCellsOfConnections.begin();it != tempCellsOfConnections.end(); ++it )
    {
      cellsOfConnection.push_back(*it);
    }
  }
}

/*int cellScore(BOARD &board, MOVE &move, int distance)
{
  int score(0);
  char color = '-';
  list<MOVE> tempList;

  for(int i=3; i>0; --i)
  {
    //horizontal - left to right
    score += countColors(board, move, 0, -i, color, tempList)+countColors(board, move, 0, i, color, tempList);
    //vertical - bottom to top
    score += countColors(board, move, -i, 0, color, tempList)+countColors(board, move, i, 0, color, tempList);
    //diagonal - top left to bottom right
    score += countColors(board, move, -i, -i, color, tempList)+countColors(board, move, i, i, color, tempList);
    //diagonal - bottom left to top right
    score += countColors(board, move, i, -i, color, tempList)+countColors(board, move, -i, i, color, tempList);
  }
  return score;
}*/

void mostIsolatedCell(BOARD &board, MOVE &move)
{
  int highestScore(-1);
  int score(0);
  MOVE tempMove;

  for(int y=0; y<10; ++y)
  {
    for(int x=0; x<10; ++x)
    {
      tempMove = pair<int,int>(y,x);
      if(board.taken(tempMove))
        continue;

      score = 0; //reset the score for this specific cell

      for(int y1 = y-2; y1 <= y+2; ++y1 )
      {
        if((y1 >= 0) && (y1 <=9))
        {
          for(int x1 = x-2; x1 <= x+2; ++x1 )
          {
            if((x1 >= 0) && (x1 <=9))
            {
              MOVE innerMove = pair<int,int>(y1,x1);
              if(!board.taken(innerMove))
                ++score;
            }
          }
        }
      }
      cout << score << endl;
      if(score > highestScore)
      {
        highestScore = score;
        move = tempMove;
      }
      else if(score == highestScore)
      {
        //find which one is closest to center, then use that one
        highestScore = score;
        move = tempMove;
      }
    }
  }
}

int gameStatus(BOARD board, MOVE move, char color, list<MOVE> &cellsOfConnection )
{
  int count(0);
  int temp(0);
  list<MOVE> tempCellsOfConnections;
  //horizontal - left to right
  temp = countColors(board, move, 0, -1, color, tempCellsOfConnections)+countColors(board, move, 0, 1, color, tempCellsOfConnections)+1;
  doStuff(count,temp, cellsOfConnection, tempCellsOfConnections );
  //vertical - bottom to top
  temp = countColors(board, move, -1, 0, color, tempCellsOfConnections )+countColors(board, move, 1, 0, color, tempCellsOfConnections)+1;
  doStuff(count,temp, cellsOfConnection, tempCellsOfConnections );
  //diagonal - top left to bottom right
  temp = countColors(board, move, -1, -1, color, tempCellsOfConnections )+countColors(board, move, 1, 1, color, tempCellsOfConnections)+1;
  doStuff(count,temp, cellsOfConnection, tempCellsOfConnections );
  //diagonal - bottom left to top right
  temp = countColors(board, move, 1, -1, color, tempCellsOfConnections )+countColors(board, move, -1, 1, color, tempCellsOfConnections)+1;
  doStuff(count,temp, cellsOfConnection, tempCellsOfConnections );
  cellsOfConnection.push_back(move);
  //cout << "count: " << count << " size:  " << cellsOfConnection.size() << endl;
  return count;
}

list<MOVE>* bustAMove(BOARD &board, MOVE move, char color, int &gameState)
{
  list<MOVE> *cellsOfConnection = new list<MOVE>;
  int count = gameStatus(board, move, color, *cellsOfConnection);
  if(count >= 4)
    gameState = WIN;
  else if(count == 3)
    gameState = LOSS;
  else 
    gameState = NOTHING;

  return cellsOfConnection;
}

list<MOVE>* userMoveHandler(BOARD &board, MOVE move, char color, int &gameState)
{
  list<MOVE> *cellsOfConnection = bustAMove(board, move, color, gameState);
  board.grid[move.first][move.second].color = color;
  return cellsOfConnection;
}

list<MOVE>* thinkingMachine(BOARD &board, MOVE &move, int &numMoves, int minNumMoves, int &gameState, char color)
{
  char userColor = (color == 'g') ? 'r' : 'g'; //switch to opposite color
  ++numMoves;
  if(numMoves > minNumMoves)
  {
    gameState = NOTHING;
    return 0;
  }
  list<MOVE> *cellsOfConnection = bustAMove(board, move, color, gameState);
  if((gameState == WIN) || (gameState == LOSS))
    return cellsOfConnection;

  board.grid[move.first][move.second].color = color;

  for(int y=0; y<10; ++y)
  {
    for(int x=0; x<10; x++)
    {      
      MOVE tempMove = pair<int,int>(y,x);
      if(board.taken(tempMove))
        continue;     

      if(opportunity(board, tempMove, 1, userColor) || opportunity(board, tempMove, 2, userColor)
                                                              || opportunity(board, tempMove, 3, userColor))
      {
        cellsOfConnection = bustAMove(board, tempMove, userColor, gameState);

        if(gameState == WIN)  //if user wins from this move, not cool, so return
        {
          gameState = LOSS;
          return cellsOfConnection;
        }
        else if(gameState == LOSS)  //if user wins from this move, not cool, so return
        {
          gameState = WIN;
          return cellsOfConnection;
        }

        ++numMoves;   //move accepted
        board.grid[y][x].color = userColor;

        for(int yz=0; yz<10; ++yz)
        {
          for(int xz=0; xz<10; xz++)
          {
              MOVE innerMove = pair<int,int>(yz,xz);
            if(board.taken(innerMove))
              continue;
            if(opportunity(board, innerMove, 1, color) || opportunity(board, innerMove, 2, color)
                                                                  || opportunity(board, innerMove, 3, color))
            {
              thinkingMachine(board, innerMove, numMoves, minNumMoves, gameState, color);
              --numMoves; //move undone
              board.grid[yz][xz].color = '-'; //undo move
            }
          }
        }
        --numMoves; //move undone
        board.grid[y][x].color = '-';     //undo move
      }
    }
  }

  gameState = NOTHING;
  return 0;
} 

list<MOVE>* getBestMove(BOARD &board, MOVE &move, char color)
{
  list<MOVE> *cellsOfConnection = new list<MOVE>;
  MOVE  bestMove = pair<int,int>(0,0); 
  int   minNumMoves(3);
  int   numMoves(0);
 // int   connectionLength(0);
  BOARD localBoard;
  int gameState = NOTHING;
  int tempGameState = NOTHING;

  for(int y=0; y<10; ++y)
  {
    for(int x=0; x<10; x++)
    { 
      move = pair<int,int>(y,x);

      if(board.taken(move))
      {
        cout << "...continue..." << endl;
        continue;
      }

      if(opportunity(board, move, 1, color) || opportunity(board, move, 2, color) || opportunity(board, move, 3, color))
      {
        localBoard = board; //for every cell, reset 
        cout << "y: " << y << " x: " << x << endl;
        numMoves = 0;
        cellsOfConnection = thinkingMachine(localBoard, move, numMoves, minNumMoves, tempGameState, color);
      
        //if(((tempGameState == WIN) && (gameState == WIN)) || ((tempGameState == NOTHING) && (gameState == NOTHING)))
        if(tempGameState == WIN)
        {
          if(numMoves < minNumMoves)
          {
            minNumMoves = numMoves;
            bestMove = move;
          }
        }
        if((tempGameState == WIN) && (gameState == NOTHING))
        {
          gameState = WIN;
          minNumMoves = numMoves;
          bestMove = move;
        }
      }
    }
  }
  
  if(gameState == NOTHING)
    mostIsolatedCell(board, bestMove);  //xxx

  cout << "bm_y: " << bestMove.first << " bm_x: " << bestMove.second << endl;

  //best move has been selected, modify the board
  board.grid[bestMove.first][bestMove.second].color = color;
  return cellsOfConnection;
}

list<MOVE>* compMoveHandler(BOARD &board, MOVE &move, char color, int &gameState)
{
  list<MOVE> *cellsOfConnection;
  char userColor = (color == 'g') ? 'r' : 'g'; //switch to opposite color

  //can computer win in one move?
  //if we dont return out of this guy, means we didn't find any cell that gives immediate victory
  for(int y=0; y<10; ++y) 
  {
    for(int x=0; x<10; ++x)
    {
      MOVE tempMove = pair<int,int>(y,x);
      if(board.taken(tempMove))
        continue;
      cellsOfConnection = bustAMove(board, tempMove, color, gameState);
      if(gameState == WIN)
      {
        move.first = y;
        move.second = x;
        board.grid[y][x].color = color;
        return cellsOfConnection;
      }
    }
  }

  int userState;
  //can the user win in one move?
  for(int y=0; y<10; ++y) 
  {
    for(int x=0; x<10; ++x)
    {
      MOVE tempMove = pair<int,int>(y,x);
      if(board.taken(tempMove))
        continue;
      bustAMove(board, tempMove, userColor, userState);
      if(userState == WIN)
      {
        cout << "user can win" << endl;
        //if opponent can win, we need to block...but we need to see if that block will cause us to lose
        cellsOfConnection = bustAMove(board, tempMove, color, gameState);
        if((gameState != LOSS) || (board.numMovesLeft() == 1))
        {
          move.first = y;
          move.second = x;
          board.grid[y][x].color = color;
          return cellsOfConnection;
        }
        else
          cout << "but computer can lose" << endl;
      }
    }
  }

  //if we get to this point, its time for us to determine our best move - there is no immediate loss/win possible
  gameState = NOTHING;
  return getBestMove(board, move, color);
}


void getUserMove(BOARD board, MOVE &move )
{
  int row(0),column(0);
  cout << "Enter a row (A-J)" << endl;
  cin >> row;
  cout << "Enter a column (1-10)" << endl;
  cin >> column;
  move = pair<int,int>(row,column);
}

void printBoard(BOARD board)
{
  cout << "  0 1 2 3 4 5 6 7 8 9" << endl;
  for(int y=0; y<10; ++y)
  {
    cout << y << " ";
    for(int x=0; x<10; ++x)
      cout << board.grid[y][x].color << " ";
    cout << endl;
  }
}

void printXCells(list<MOVE> cellsOfConnection)
{
  for(list<MOVE>::const_iterator it = cellsOfConnection.begin(); it!= cellsOfConnection.end(); ++it)
    cout << it->first << " " << it->second << endl;
}

int main (int argc, char *argv[])
{
  char         wannaPlay('y');
  cout  <<    "Do ya wanna wanna playyyy? (y or n)" << endl; 
  cin   >>    wannaPlay;

  while(wannaPlay == 'y')
  {
    BOARD     board;
    PLAYER    user;
    PLAYER    computer;
    MOVE      move(0,0);
    char      response;
    char      color('-');
    //list<MOVE> *cellsOfConnection;
    int       gameState = NOTHING;

  /*  board.grid[7][2].color = 'g';
    board.grid[6][3].color = 'g';
    board.grid[0][0].color = 'r';
    board.grid[0][1].color = 'r';

    board.grid[0][0].color = 'r';
    board.grid[0][3].color = 'r';
    //board.grid[9][9].color = 'g';
    board.grid[5][5].color = 'g';
    //board.grid[5][5].color = 'r';
    board.grid[5][6].color = 'r';
    board.grid[6][2].color = 'r';
    board.grid[5][4].color = 'r';
    board.grid[2][5].color = 'g';
    board.grid[4][4].color = 'g';
    board.grid[4][5].color = 'g';
    board.grid[6][5].color = 'g';
    board.grid[7][6].color = 'g';
    board.grid[1][5].color = 'g';

    printBoard(board);

    int distance;
      cout << "distance?" << endl;
      cin >> distance;
      color = 'g';
      move = pair<int,int>(9,9);  
      opportunity( board,  move,  distance,  color) ? cout << "true" : cout << "false";
      cout << endl;

    */

   /* color = 'r';
    int gameState;
    //move = pair<int,int>(1,5);  
    printBoard(board); cout << "\n"; 
    cellsOfConnection = bestMoveHandler(board, move, color, gameState); 
    printBoard(board); 
    printXCells(*cellsOfConnection);
    delete cellsOfConnection;
    
    endOfGame(board, gameState, color);
      
    move = pair<int,int>(3,5);  
    printBoard(board); cout << "\n"; 
    cellsOfConnection = bustAMove(board, move, color, gameState); 
    printBoard(board); 
    printXCells(*cellsOfConnection);
    delete cellsOfConnection;

    endOfGame(board, gameState, color);*/

   /* move = pair<int,int>(8,6);
    printBoard(board); cout << "\n"; bustAMove(board, move, color, gameState); printBoard(board);
    
    move = pair<int,int>(8,7);
    printBoard(board); cout << "\n"; bustAMove(board, move, color, gameState); printBoard(board);
   */ 
    cout  <<  "Green or Red flavored? (g or r)" << endl;              //prompt user for desired color
    cin   >>  user.color; 
    (user.color == 'g') ? computer.color = 'r' : computer.color = 'g';//set computer to opposite color

    cout  <<  "You wan go first? (y or n)" << endl;                   //prompt user to decide first player
    cin   >>  response;
    (response == 'y') ? user.currentTurn = 1 : computer.currentTurn = 1;
    color = (user.currentTurn) ? user.color : computer.color;

    printBoard(board);

    while( !endOfGame(board, gameState, color) )                             //play one game
    {
      //printBoard(board);
      color = (user.currentTurn) ? user.color : computer.color;
      
      if (computer.currentTurn)                                       //computer turn
      {
        compMoveHandler(board, move, color, gameState);    
        printBoard(board);
      }
      else                                                            //user turn
      {
        getUserMove(board, move); 
        cout << move.first << " " << move.second << endl;
        userMoveHandler(board, move, color, gameState);
        printBoard(board);
      }
      
      user.currentTurn = !user.currentTurn;
      computer.currentTurn = !computer.currentTurn;
    }
    //delete board[][];
    cout  << "Do ya wanna wanna playyyy? (y or n)" << endl; 
    cin   >> wannaPlay;
    
  }
  return 0;
}
